package 剑指offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class p33二叉搜索树的后序遍历序列 {
    public boolean verifyPostorder(int[] postorder) {
        if (postorder.length<1) {
            return false;
        }
        //将数组转为 链表/顺序表，因为后面根据左右子树进行划分
        List<Integer> tree=new ArrayList<>(); //new LinkedList<>()也可以，顺序表更快
        for (int num:postorder) {
            tree.add(num);
        }

        return justify(tree);
    }

    private boolean justify(List<Integer> tree) {
        if (tree.size()<1) {
            //递归出口：当前子树数组没有节点时
            return true;
        }

        int rootIndex=tree.size()-1;
        int root=tree.get(rootIndex);//获取当前树根节点的值

        List<Integer> leftTree=new LinkedList<>();
        List<Integer> rightTree=new LinkedList<>();

        int i=0;
        //左子树的值都 小于 当前根节点的值
        while (tree.get(i)<root){
            leftTree.add(tree.get(i));
            i++;
        }

        //右子树的值都 大于 当前根节点的值
        while (tree.get(i)>root) {
            rightTree.add(tree.get(i));
            i++;
        }

        if (i<rootIndex) {
            return false;//证明
        }

        return justify(leftTree) && justify(rightTree);
    }


}
